package DataStructure.array;

/**
 * 169. 多数元素 https://leetcode.cn/problems/majority-element
 * 题目简述：一个大小为n的数组nums中存在一个出现次数大于⌊n/2⌋的多数元素，找出它。
 */
public class MajorityElement {

    /**
     * 思路：对拼投票法，初始候选人为nums[0]，票数为1，遇上相同元素票数增1，不同元素票数减1，票数为0后下一个元素成为候选人，
     *      最后数组中票数过半的元素一定当选（最坏情况所有其他元素都由这个元素对拼掉了）
     */
    public int majorityElement(int[] nums) {
        int cand = nums[0], voteNum = 1;//初始候选人为nums[0]，票数为1
        for(int i=1;i < nums.length;i++) {
            if(voteNum == 0) cand = nums[i];//检查票数，若为0则当前元素成为候选人
            if(nums[i] == cand)
                voteNum++;//相同加票
            else {
                voteNum--;//不同则减票
            }
        }
        return cand;
    }
}
